package com.aqie.arithmetic.sort;

/**
 * 希尔排序
 */
public class ShellSort extends SortTest{

    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3){
            h = 3 * h + 1;
        }

        while (h >= 1){
            for (int i = h; i < N; i++){
                // 将a[i] 插入到a[i-h] a[i-2*h], a[i-3*h]
                for (int j = i; j >= h && less(a[j], a[j-h]);j -=h){
                    exch(a, j, j - h);
                }
            }
            h /= 3;
        }
    }

    public static void main(String[] args) {
        new ShellSort().process(10);
    }
}
